package P1.guibingpaixu;

import java.util.Scanner;

/**
 * @date:2022/8/24
 * @author:LdLtd
 * @name:归并排序
 */
public class MergeSort {
    public static void main(String [] args){
        Scanner scanner =new Scanner(System.in);
        int n=scanner.nextInt();
        int [] q=new int[n];
        int [] t=new int[n];
        for(int i=0;i<n;i++){
            q[i]=scanner.nextInt();
        }
        merge_sort(q,0,n-1,t);
        for(int i=0;i<n;i++){
            System.out.print(q[i]+" ");
        }

    }
    public static void merge_sort(int[]q,int l,int r,int[] t){
        if(l>=r) return;
        int mid =l+r>>1;
        merge_sort(q,l,mid,t);
        merge_sort(q,mid+1,r,t);
        int k=0,i=l,j=mid+1;
        while (i<=mid&&j<=r){
            if(q[i]<=q[j]) t[k++]=q[i++];
            else t[k++]=q[j++];
        }
        //循环完，剩余的全部放进去
        while(i<=mid) t[k++]=q[i++];
        while(j<=r) t[k++]=q[j++];
        //放回原数组
        for(i=l,j=0;i<=r;i++,j++) q[i]=t[j];

    }

}
